package com.ywk.base.dataStructure.search;

import java.util.ArrayList;
import java.util.List;

//二分查找：数组元素必须有序
public class BinarySearch {

	public static void main(String[] args) {
		int[] nums= {1,3,6,8,8,10,15,15,19,25,30,30,37};
		List<Integer> result=binarySearch(nums, 0, nums.length-1, 8);
		System.out.println("indexs="+result);
	}
	
	public static List<Integer> binarySearch(int[] nums,int left,int right,int num) {
		List<Integer> index=new ArrayList<Integer>();
		int mid=(left+right)/2;
		if (left <= right) {
			if (nums[mid] == num) {
				//System.out.println("找到了，下标为：" + mid);
				index.add(mid);
				int temp=mid-1;
				//向左扫描
				while(nums[temp]==num) {
					index.add(temp);
					temp--;
				}
				temp=mid+1;
				//向右扫描
				while(nums[temp]==num) {
					index.add(temp);
					temp++;
				}
			} else if (num < nums[mid]) {
				//当递归中需要返回值时，在递归的方法前添加return
				return binarySearch(nums, left, mid - 1, num);
			} else if (num > nums[mid]) {
				return binarySearch(nums, mid + 1, right, num);
			}
		}
		return index;
	}
}
